package leetcode;

/**
 * @author caifangyi
 * @date 2022/7/25
 */

/**
 * 1184. 公交站间的距离
 * 
 * 环形公交路线上有n个站，按次序从0到n - 1进行编号。我们已知每一对相邻公交站之间的距离，
 * distance[i]表示编号为i的车站和编号为(i + 1) % n的车站之间的距离。
 *
 * 环线上的公交车都可以按顺时针和逆时针的方向行驶。
 *
 * 返回乘客从出发点start到目的地destination之间的最短距离。
 *
 * 
 *
 * 示例 1：
 *
 *
 *
 * 输入：distance = [1,2,3,4], start = 0, destination = 1
 * 输出：1
 * 解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
 * 
 *
 * 示例 2：
 *
 *
 *
 * 输入：distance = [1,2,3,4], start = 0, destination = 2
 * 输出：3
 * 解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
 * 
 *
 * 示例 3：
 *
 *
 *
 * 输入：distance = [1,2,3,4], start = 0, destination = 3
 * 输出：4
 * 解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
 * 
 *
 * 提示：
 *
 * 1 <= n<= 10^4
 * distance.length == n
 * 0 <= start, destination < n
 * 0 <= distance[i] <= 10^4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/distance-between-bus-stops
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Day1184 {

    public static void main(String[] args) {
        int nums[] = {6,47,48,31,10,
                27,46,33,52,33,
                38,25,32,45,36,
                3,0,33,22,53,8,
                13,18,1,44,41,
                14,5,38,25,48};
        Solution2 solution = new Solution2();
        int i = solution.distanceBetweenBusStops(nums, 22, 0);
        System.out.println(i);
    }

    static class Solution2{
        public int distanceBetweenBusStops(int[] distance, int start, int destination) {
            if(start > destination){
                start = start^destination;
                destination = start^destination;
                start = start^destination;
            }
            int sumL = 0, sumR = 0;
            for (int i = 0; i < distance.length; i++) {
                if(i>=start && i<destination){
                    sumL+=distance[i];
                }else{
                    sumR+=distance[i];
                }
            }
            return Math.min(sumL, sumR);
        }
    }

    static class Solution {
        public int distanceBetweenBusStops(int[] distance, int start, int destination) {
            //可正向，也能反向，两种同时计算，当其中一种到达终点，另一种路程超过且未到终点，则抛弃
            int length = distance.length;
            int startL = start, startR = start;
            int sumL = 0, sumR = 0;
            while(!((startL==destination && sumL<sumR) ||
                    (startR==destination && sumR<sumL))){
                if(startL != destination){
                    if(startL == 0){
                        startL = length;
                    }
                    sumL+=distance[--startL];
                }
                if(startR != destination){
                    sumR+=distance[startR++];
                    if(startR == length){
                        startR = 0;
                    }
                }
            }
            return Math.min(sumL, sumR);

        }
    }
}
